1. Field of the Invention
The present invention is related to interleavers used in systems such as communication systems.
2. Description of the Related Art
Interleavers are processing entities that manipulate data or information in a certain well defined manner. Interleavers alter the time order of the data or information. A block of information (or data) is typically arranged as a plurality of consecutive sub-blocks having a proper order. An interleaver re-arranges the time order of these sub-blocks in accordance with a specific pattern. The pattern is a well defined deterministic pattern, and sometimes it is a pseudorandom pattern. The process of interleaving is used in many information processing systems including wireless and wireline communication systems.
It is well known in communication systems to code information prior to their transmission over communication channels. The coding of information prior to transmission over a communication channel is a well known technique used by communication system designers to make the information less vulnerable to noise that may exist in the channel. An example of coding, which is used particularly in wireless communication systems, is turbo coding and decoding. Turbo coding, in part, uses the interleaving process to add redundancy to the information and increase the codeword weight in a particular manner. A codeword is formed when information bits in a code block are used to generate parity bits where the resultant redundant parity bits are combined with the information bits to form a code word. The weight of a code word is defined as the minimum distance between any two code words; the weight is also referred to as the Hamming weight. Interleavers are thus a key component of turbo encoders and decoders.
The basic approach to the design of interleavers is to first store the information (i.e., sub-blocks of the information) in known memory locations or memory addresses. The contents of the memory locations are then retrieved in accordance with some predefined pattern that can be random, pseudorandom or deterministic. By retrieving the stored memory addresses in accordance with the pattern, the corresponding sub-blocks of information are retrieved in accordance with the pattern thus achieving the interleaving of the information. The interleaver address pattern can change depending on the length of the sub-block of data in many interleaver implementations. Hence, a separate address pattern for each possible block length would be needed.
Various circuits or algorithms are used to generate the address pattern that indicates which particular order the stored information is to be retrieved. Many pseudorandom interleaver designs are implemented using Digital Signal Processors (DSP) and lookup tables to calculate the interleaving addresses in accordance with a pattern. An interleaver can also be implemented using an SRAM (Static Random Access Memory), a ROM (Read Only Memory), an EPROM (Erasable Programmable Read Only Memory) or any other memory containing the scrambling addresses. Thus, the conventional approach to designing interleavers uses ROMs, RAMs or other memory circuits in which the interleaver addresses are stored.
When implemented with ROMs, the contents of the locations (i.e., interleaver addresses) in the ROM are pre-calculated offline during the design of the interleaver and hard-coded into the memory for all possible block lengths. When implemented with RAMs, the contents of the locations of the RAM can either be populated with pre-calculated address locations for all possible block lengths or the address locations can be calculated by a separate processor ( e.g., Digital Signal Processor (DSP)) at runtime for each block length's specific pattern as it is needed. The contents of the memory locations in either the RAMs or the ROMs are pointers that point to certain addresses thus implementing a particular interleaving pattern. As previously stated, the interleaving pattern can be pseudorandom. In some current wireless communication systems, pseudorandom patterns for interleavers are used as part of the turbo coding and decoding operations. In particular, the 3rd Generation Partnership Project (3GPP) group has promulgated the Group Radio Access Network Standard TS 25.212 V4.2.0 (2002-09) wherein a specific procedure for generating a pseudorandom pattern for interleavers used in turbo coders and decoders is disclosed. Specifically, certain interleaving parameters are defined and the particular method of calculation of these parameters is also defined in sub-sections 4.2.3.2.3.1-4.2.3.2.3.3.
A common method of generating pseudorandom interleaving patterns relies heavily on the use of the MOD (modulus) operation. The MOD operation is a well known operation in residue number theory. The result of the MOD operation is a remainder after an arithmetic division operation is performed. The MOD operation is defined in the following manner:
      a    ⁢                  ⁢    MOD    ⁢                  ⁢    b    ≡      remainder    ⁢                  ⁢    of    ⁢                  ⁢                  a        b            .      Thus, for example 12 MOD 4=0 because 12 divided by 4 equals 3 with remainder 0; another example is 12 MOD 5=2; 135 MOD 6=3 and so on. The MOD operation is implemented using division or several steps of addition, comparison and subtraction which require more than one clock cycle to achieve. Also, MOD operations require relatively large amounts of computing/processing power and circuit area in order to compute a MOD value relatively quickly. For example, in one implementation where MOD operations (up to mod 33) are implemented using hardware, 20.6 mm2 of silicon may be required. Also, because the computing process usually takes several clock cycles to complete a single MOD operation, an undesirable delay is usually introduced.
Interleaver designs in which pseudorandom interleaving patterns for different information lengths are considered are usually implemented with ROMs or RAMs that use (1) relatively large amounts of processing power (2) relatively large amounts of circuit space and/or a DSP and (3) introduce substantial amounts of delay in the processing time. Interleavers that can generate addresses as per a defined pattern without having to pre-populate a RAM or ROM thus avoiding the just mentioned disadvantages are therefore desirable.
A turbo interleaver address generator designed in accordance with the 3GPP (Third Generation Partnership Project) wireless standard is part of known art. The interleaver disclosed in the known art is able to generate addresses that follow a specific pattern (specified in sub-sections 4.2.3.2.3.1-4.2.3.2.3.3 of the 3GPP standard) which has been determined by the 3GPP standard to have desirable random probabilistic characteristics.
The interleaver address generator disclosed in the known art is able to calculate interleaver addresses (based on the 3GPP defined interleaver parameters) on an as-needed basis (“on the fly”) using a relatively small amount of hardware; the known art interleaver address generator generates an address every clock cycle. The ability to calculate interleaver addresses on the fly using a relatively small amount of hardware results in a significant improvements in (a) power consumption, (b) latency in processing and (c) size of circuitry. The interleaver address generator disclosed in the known art uses certain 3GPP standard defined interleaver parameters as inputs and generates the interleaver addresses based on these inputs. Because the interleaver address generator disclosed in the known art calculates addresses on an as-needed basis (i.e., on the fly), the interleaver parameters that it uses to calculate such addresses have to be available on the fly or have to be calculated on the fly.
One of the parameters used by the known art interleaver address generator is K which represents the block length of the information to be interleaved. As new blocks of information to be interleaved arrive, the value of K changes because typically the blocks of information have varying lengths. The remaining parameters as defined in the standard (discussed infra) are calculated based on the value of K. Thus, in order for the interleaver address generator to calculate addresses on the fly, a new set of parameters have to be calculated and made available for a new value of K. The terms “on the fly” or “on an as-needed basis” refer to the calculation of new parameters for new values of K and making such parameters immediately available or at least available prior to the arrival of a new and different K.
As described in sub-sections 4.2.3.2.3.1-4.2.3.2.3.3 of the 3GPP standard, a block of information of length K is to be stored in a matrix having R rows and C columns (i.e., an R×C matrix). Thus, K, R and C are interleaver parameters used to calculate the interleaver addresses. Different portions of the block of information of length K are stored in the matrix and such portions are retrieved in a certain order that complies with a pattern defined by the standard. In addition to K, R and C, the standard defines additional parameters that are used to calculate the interleaver addresses. K is given; i.e., it represents the length (in number of bits) of the block of information to be interleaved. The remaining parameters are determined as follows:
Determining R (Number of Rows in the Matrix)
    If (40≦K≦159) the R=5;    If (160≦K≦200) or (481≦K≦530) then R=10;    If (K=any other value) then R=20.At this point both K and R are known. According to the standard, the smallest possible prime number, p, that satisfies the condition
      p    +    1    ≥      K    R  is to be selected from a table. The table which is given by the standard is as follows:
pVpvpvPvpv734751012157522331125321035163222721325921072167522961736121096173223331926721133179223972357171273181224172927351312191192516313793137319352573372832139219724168931492199343397515162112
As can be seen from the table, each value for p has an associated value for a parameter, v. Parameter v is a primitive root for a prime number, p. The parameter p and its associated primitive root, v, are intermediate parameters defined by the standard so as to provide the proper amount of randomness to the interleaver addresses that are generated based on such intermediate parameters.
Determining C (Number of Columns in the Matrix)
    If (K≦R (p−1)) then C=p−1;    If (R(p−1)<K≦R·p) then C=p;    If (R·p<K) then C=p+1.Determining the PRUNVAL Parameter
The matrix (R×C) determined from interleaver parameters may have more space than needed to store the K bit information block. A parameter known as PRUNVAL (pruning value) is calculated and is equal to the number of matrix locations that can be eliminated from the R×C matrix. Typically, the matrix locations at the end of the matrix are the ones that are pruned (i.e., eliminated). The pruning value is defined as ((R·C)−K).
Determining the S(i) Parameter for i=[0,1, . . . , p−2]
A parameter that is a sequence of values is also used to generate the interleaver addresses. Each interleaver address that is generated uses one value from this sequence of values to provide the interleaver address pattern being generated with the proper randomness dictated by the 3GPP standard. The sequence of values is referred to as S(i) (“Sequence of i”) and it is derived from the value of K. More specifically, S(i) is defined recursively as equal to (v·S(i−1)) MOD p where S(O)=1 and i=[1, . . . , p−2]. Note that if K is known, then as described above, p can be determined and thus v is also determined which allows S(i) to be calculated. There can be up to 256 values for S(i) (i.e., when p=257), for a particular value of K, which represents a relatively large number of MOD operations.
MOD operations are essentially division operations which are typically implemented with relatively complex circuitry. Further, a circuit that can accommodate up to 255 MOD operations is not only complex but uses a relatively large amount of space and power. Moreover, the value of K typically changes as new blocks of information to be interleaved are applied to the interleaver. Therefore, for each new value of K, a new S(i) sequence and also new parameters (i.e., p, v, R, C) have to be calculated. Consequently, relatively large amounts of calculations using complex operations such as the MOD operations have to be performed every time K changes.
A known interleaver address generator requires, for each new value of K, the S(i) sequence to be calculated using a separate DSP along with memory circuitry to which the S(i) values are transferred. The interleaver address generator disclosed in the known art calculates addresses on an as-needed basis (i.e., “on the fly”) to avoid large power hungry memory circuits. Because the interleaver in the known art calculates the interleaver addresses on the fly, the S(i) values for a particular value of i are available when needed by the interleaver address generator. Thus for each particular K value, the S(i) sequence is calculated externally (e.g., by a DSP) and stored in a memory circuit where particular S(i) values can be selected on the fly by the interleaver address generator disclosed in the known art. This interaction is time consuming and requires the use of a DSP, for which many MIPs (Million of Instructions per second) can be consumed by this process of calculating the S(i) values and filling the memory every time K changes.
Another possible approach for generating the S(i) sequence and the other parameters so that they are available on an as-needed basis would be to pre-calculate the parameters (including the S(i) sequence) for all possible values of K and store these values in memory circuits; it is clear that this approach would require a large amount of circuitry to implement. What is therefore needed is a hardware circuit that can calculate the interleaver parameter S(i) and the other parameters on an as-needed basis (on the fly) without having to use a separate DSP or without having to generate a relatively large table containing the parameters values for different values of block length or information length.